A stream of video data to be encoded is illustrated schematically in FIG. 1a. The stream comprises multiple frames (F) each representing the video image at a different respective moment in time. As will be familiar to a person skilled in the art, for the purpose of encoding, each frame (F) is divided into portions and each portion may also be subdivided into smaller sub-portions, each portion or sub-portion comprising a plurality of pixels. For example, according to one terminology each frame of a video stream to be encoded is divided into macroblocks (MB) and each macroblock is sub-divided into blocks (b), each block comprising multiple pixels. Each frame may also be divided into independently decodable slices (S), each slice comprising one or more macroblocks. N.B. the divisions shown in FIG. 1a are only schematic for illustrative purposes and it will be appreciated that these are not necessarily meant to correspond to any actual encoding scheme—e.g. each frame is likely to contain a larger number of macroblocks.
A goal of a video codec is to reduce the bit rate needed to transmit a video signal, while maintaining highest possible quality. This goal is achieved by exploiting statistical redundancies (similarities in the video signal) and perceptual irrelevancies (related to sensitivity of human visual system).
Most of today's video codecs are based on an architecture that includes prediction of pixel blocks from other pixel blocks, transform of prediction residuals, quantization of transform coefficients, and entropy coding of quantization indices. These steps contribute to reducing redundancies and irrelevancies.
The prediction typically can be done from pixels in video frames different from the current frame (inter prediction) and from pixels in the same frame (intra prediction). That is, if encoded using intra frame encoding then a block or portion of the frame (the target block or portion) is encoded relative to another block or image portion in the frame (the reference block or portion); and if encoded using inter frame encoding then the target block or portion is encoded relative to a reference block or portion in another frame. This process is commonly referred to as prediction or prediction coding. The inter or intra prediction module will thus generate a prediction e.g. in the form of an indication of a neighbouring block in the case of intra frame encoding and/or a motion vector in the case of inter frame encoding. Typically the encoder also generates a residual signal representing a “left over” difference between the predicted block and the actual block. The intra prediction, motion vectors and residual are then output into the encoded video stream, typically via further coding stages such as a quantizer and entropy encoder. Hence most blocks in the video can be encoded in terms of a difference between blocks, which requires fewer bits to encode than encoding absolute pixel values and hence saves on bitrate. Intra prediction encoding typically requires more bits than inter prediction, though still represents a saving over encoding absolute values. Details of suitable inter and intra encoding techniques for video will be familiar to a person skilled in the art.
Modern codecs allow the use of different prediction encoding modes for different portions within a frame. The possibility of having different coding options increases the rate-distortion efficiency of a video codec. The optimal coding representation has to be found for every frame region. Typically, such region is a macroblock, e.g. of 16×16 pixels. I.e. so it is possible for an intra prediction or inter prediction mode to be selected individually for each macroblock, so that different macroblocks within the same frame can be encoded with different modes. It is also possible in some codecs to use different modes based on different levels of partitioning of macroblocks, e.g. selecting between a higher complexity mode in which a separate prediction is performed for each 4×4 block within a macroblock or a lower complexity mode in which prediction is performed based on only 8×8 or 8×16 blocks or even whole macroblocks. The available modes may also include different options for performing prediction. For example as illustrated schematically in FIG. 1b, in one intra mode the pixels of a 4×4 block (b) may be determined by extrapolating down from the neighbouring pixels from the block immediately above, or by extrapolating sideways from the block immediately to the left. Another special prediction mode called “skip mode” may also be provided in some codecs, which may be considered as an alternative type of inter mode. In skip mode (PSkip) the target's motion vector is inferred based on the motion vectors to the top and to the left and there is no encoding of residual coefficients. The manner in which the motion vector is inferred is consistent with motion vector prediction, and thus the motion vector difference is zero so it is only required to signal that the MB is a skip block.
According to the above, a coding representation may thus include block partition information, prediction mode, motion vector, quantization accuracy, etc. The optimal coding option depends on video content, bit rate, earlier coding decisions, etc. The accuracy of quantization of transform coefficients is typically chosen to meet a bit rate constraint. Furthermore, distortion should be minimized.
For example, the H.264 video coder provides a great flexibility in choosing the prediction mode. For inter prediction of the luma component, a macroblock of 16×16 pixels can be represented as one block of 16×16 pixels, or two blocks of 16×8 pixels, or two blocks of 8×16 pixels, or four blocks of 8×8 pixels. Further, an 8×8 block can be represented as one block of 8×8 pixels, or two blocks of 8×4 pixels, or two blocks 4×8 pixels, or four blocks of 4×4 pixels. The inter prediction is tried for each allowed partition of a macroblock. The inter prediction of a block is represented by indexing the reference frame(s) and the motion vector(s) (spatial shift from the reference block in the respective reference frame), which typically are estimated with sub-pixel precision. For intra prediction of the luma component, there are four possible modes for 16×16 blocks and nine possible modes for 4×4 blocks. Further, there are four possible modes for chroma components. The best prediction mode is chosen by comparing the performance of inter and intra prediction modes.
The rate-distortion performance of a video codec such as H.264 AVC depends to a large extent on the performance of the macroblock mode selection o. That is, the procedure of determining whether the macroblock is best encoded, in terms of rate-distortion trade-offs, using e.g. intra mode or inter mode (predicted from previously encoded frame). From a robustness perspective, intra coded macroblocks are beneficial since they stop temporal error propagation (assuming the use of constrained intra prediction, i.e. intra prediction from inter predicted macroblocks is prohibited). However, intra coded macroblocks are generally more expensive in terms of rate compared to inter coded macroblocks, and thus it is important to introduce intra coded macroblocks systematically such that the distortion (e.g. average distortion) at the decoder is minimized given a certain bit budget.
The rate-distortion performance optimization problem can be formulated in terms of minimizing distortion under a bit rate constraint R. A Lagrangian optimization framework is often used to solve the problem. There, the optimization criterion is formulated asJ=D(m,o)+λR(m,o),  (1)where J represents the Lagrange function, D represents a measure of distortion (a function of mode o and macroblock m or macroblock sub-partition), R is the bitrate, and λ is a parameter defining a trade-off between distortion and rate.
In this application solving the Largrangian optimization problem means finding the encoding mode o which minimizes the Lagrange function J, where the Lagrange function J comprises at least a term representing distortion, a term representing bitrate, and a factor (the “Lagrange multiplier”) representing a tradeoff between the two. As the encoding mode o is varied towards more thorough or better quality encoding modes then the distortion term D will decrease. However, at the same time the rate teen R will increase, and at a certain point dependent on the increase in R will outweigh the decrease in D. Hence the expression J will have some minimum value, and the encoding mode o at which this occurs is considered the optimal encoding mode.
In this sense the bitrate R, or rather the term λR, places a constraint on the optimization in that this term pulls the optimal encoding mode back from ever increasing quality. The mode at which this optimal balance is found will depend on λ, and hence λ may be considered to represent a tradeoff between bitrate and distortion.
The Lagrangian optimization is commonly used in the process of choosing coding decisions, and is applied for every frame region (e.g. every macroblock of 16×16 pixels).
The distortion D may be quantified as sum of squared differences (SSD) between original and reconstructed pixels; and may be evaluated to account for all processing stages including: prediction, transform (from a spatial domain representation of the pixels of each block or macroblock to a transform domain representation such as an optical frequency domain representation), and quantization (the process of converting a digital approximation of a continuous signal to more discrete, lower granularity quantization levels). Furthermore, in order to compute reconstructed pixels, steps of inverse quantization, inverse transform, and inverse prediction must be performed. Commonly, the rate term R also accounts for coding of all needed parameters, including parameters describing prediction and quantized transform coefficients.
Parameters are typically coded with an entropy coder, and in that case the rate can be an estimate of the rate that would be obtained by the entropy coder, or can be obtained by actually running the entropy coder and measuring the resulting rate for each of the candidate modes. Entropy coding/decoding is a lossless process and as such doesn't affect the distortion.
This kind of process may be referred to herein as a full complexity rate-distortion optimization (or full RDO).
In one particular example disclosed by Zhang et al., “Error resilience video coding in H.264 encoder with potential distortion tracking”, In Proc. IEEE International Conference on Image Processing, pp. 163-166, 2004, incorporated herein by reference in its entirety. The distortion term may take into account not just the source coding distortion intrinsic to the codec but also end-to-end distortion, i.e. a probabilistic estimate of distortion that will be experienced due to packet loss over a channel. However this is not a requirement for “full” complexity RDO.
It will be seen from everything discussed above that the number of coding options can be quite high, and therefore the computational load needed to evaluate them can become a limiting factor. Given a high number of possible coding options, evaluating the Lagrangian optimization criterion that accounts for all processing stages (and also requires all inverse processing stages to be performed) can become a computationally very demanding task. Therefore, an alternative lower-complexity optimization criterion is also in common use:J′=D′(m,o)+λ′R′(m,o)  (2)where D′ is the prediction distortion, and R′ is the rate for parameters describing prediction (e.g., prediction modes, motion vectors). R′ does not take the rate of residual coefficients into account.
The prediction distortion D′ takes into account only the distortion after the intra or inter prediction (or more precisely the residual after prediction), and not the effect of other encoder stages such as transform from the spatial domain and quantization (nor their inverses). Further, this simplified distortion measure is quantified as the sum of absolute differences (SAD) between the original and predicted samples, which requires fewer computations compared to SSD. That is:
                              D          ′                =                              ∑            i                    ⁢                                                                s                i                            -                              s                                  pred                  i                                ′                                                                                    (        3        )            where si are the original input samples and spred′i are the predicted samples without taking into account the effect of being reconstructed through a forward and inverse transform and quantization. So as well as being based on SAD instead of SSD, the lower complexity distortion term D′ represents the difference between the original and predicted samples, rather than the difference between original and reconstructed pixels as represented in the full complexity version of the calculation above.
Further, the rate term R′ only represents the bitrate cost of side information (motion vector or indication of intra prediction, prediction mode, and indication of macroblock partitioning); and does not take into account the bitrate cost of the transformed and quantized residual.
Thus, the simplified computation only needs the prediction step to be performed. The steps of transform and quantization, as well as inverse quantization, inverse transform, and inverse prediction are omitted. Hence the complexity of evaluating performance of a coding option is therefore reduced. This kind of process may be referred to herein as low-complexity rate-distortion optimization (or low-complexity RDO).
On the other hand, since low-complexity RDO approximates the prediction step only, the resulting final rate-distortion performance is typically reduced. Without being limiting, in the inventors' experiments they have observed that the low-complexity RDO may result in performance drop of 0.5-1.5 dB compared to the full RDO at the same bit rate. Subjectively, the reconstructed videos also have lower quality.